package l.l.w.leetcode._300LongestIncreasingSubsequence;

import java.util.Arrays;

public class _300LongestIncreasingSubsequence {
    /**
     * 使用最长公共子序列A.
     * 将原来的数组另存一份，然后排序，去重，作为B。
     * 寻找A与B的最长公共子序列即可
     * 时间复杂度高，空间复杂度也高
     * @param nums
     * @return
     */
    public int lengthOfLISUseLTS(int[] nums){
        if(nums == null || nums.length == 0) return 0;
        int[] temps = new int[nums.length];
        for(int i = 0; i < nums.length;++i){
            temps[i] = nums[i];
        }
        Arrays.sort(temps);
        int pre = temps[0];
        for(int i = 1; i < nums.length;){
            if(temps[i] == pre){
                temps[i++] = Integer.MIN_VALUE;
            }else{
                pre = temps[i++];
            }
        }
        int k = 1;
        for(int i = 1; i < temps.length;++i){
            if(temps[i] != Integer.MIN_VALUE){
                swap(temps,i,k++);
            }
        }
        int len = nums.length;
        int[][] dp = new int[len+1][k+1];
        for(int i = 1; i <= len; ++i){
            for(int j = 1; j <= k; ++j){
                if(nums[i-1] == temps[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        return dp[len][k];
    }

    private void swap(int[] temps, int i, int k) {
        int temp = temps[i];
        temps[i] = temps[k];
        temps[k] = temp;
    }

    /**
     * 使用动态规划。 dp[i]表示以nums[i]结尾的的数组的最长递增子序列
     *     dp[i] = max(dp[i]) + 1,i < j, 且 nums[i] > nums[j];
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums){
        if(nums == null || nums.length == 0) return 0;
        int result = 0;
        int len = nums.length;
        int[] dp = new int[len];
        for(int i = 0; i < len; ++i){
            dp[i] = 1;
            for(int j = 0; j < i; ++j){
                if(nums[i] > nums[j] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                }
            }
        }
        for(int i = 0; i < len; ++i){
            if(dp[i] > result){result = dp[i];}
        }
        return result;
    }
    public static void main(String[] args){
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
//        int[] nums = {4,4,4,4};
//        int[] nums = {-2,-1};
        int result = new _300LongestIncreasingSubsequence().lengthOfLIS(nums);
        System.out.println("result: " + result);
    }
}
